A computer network is a geographically distributed collection of interconnected subnetworks, such as local area networks (LAN) that transport data between network nodes. As used herein, a network node is any device adapted to send and/or receive data in the computer network. The network topology is defined by an arrangement of inter-connected network nodes that communicate with one another, typically through one or more intermediate nodes, such as routers and switches. Adjacent (“neighboring”) network nodes may be interconnected by various types of data links, such as conventional wire links, optical links, wireless links, etc. The network nodes typically communicate by exchanging discrete packets of data over the data link using predefined network communication protocols. In this context, a protocol consists of a set of rules defining how network nodes interact with each other.
A computer network may contain smaller groups of one or more subnetworks which may be managed as separate routing areas. As used herein, a routing area is broadly construed as a collection of interconnected network nodes under a common administration. Accordingly, a routing area also may be generally referred to as a routing domain or routing level. A routing area may operate as an enterprise network, a service provider or any other type of network or subnetwork. Often, a routing area is managed by a single administrative entity, such as a company, an academic institution or a branch of government. Such a centrally-managed routing area is sometimes referred to as an “autonomous system” (AS).
Network nodes in a routing area are typically configured to forward data using “interior gateway” routing protocols. These interior gateway protocols (IGP) define the manner with which routing information and network-topology information is exchanged and processed in the routing area. For instance, IGP protocols typically provide a mechanism for distributing network address information corresponding to a set of nodes and subnetworks that are reachable (i.e., accessible) to intermediate nodes in the routing area. As such, each intermediate node receives a consistent “view” of the routing area's topology. Examples of interior gateway routing protocols include conventional link-state protocols, such as the Open Shortest Path First (OSPF) protocol and the Intermediate-System-to-Intermediate-System (IS-IS) protocol. The OSPF and IS-IS protocols are described in more detail in the Internet Engineering Task Force (IETF) publications Request for Comments (RFC) 2328, entitled “OSPF Version 2,” published April 1998 and RFC 1142, entitled “OSI IS-IS Intra-domain Routing Protocol,” published February 1990, both of which are hereby incorporated by reference as though fully set forth herein.
Conventional link-state protocols, such as OSPF and IS-IS, use IGP advertisements for exchanging routing information between interconnected intermediate network nodes (IGP nodes) in a routing area. As used herein, an IGP advertisement describes any message used by an IGP routing protocol to communicate routing information and/or network-topology information among the interconnected IGP nodes. An IGP node typically generates an IGP advertisement in response to a network event, such as a detected node or link failure, and in some cases may generate its IGP advertisements periodically. Operationally, a first IGP node may generate an IGP advertisement and then “flood” (i.e., transmit) the advertisement to each of its directly-connected IGP nodes (neighboring IGP nodes). Thereafter, a neighboring IGP node receives the flooded advertisement and updates its local set of routing information based on the contents of the received advertisement. Next, the neighboring IGP node may flood the received IGP advertisement to each of its directly-connected IGP nodes, except for the node which previously flooded the advertisement. This process may be repeated until each IGP node in the routing area has received the advertisement and updated its local routing information.
Each IGP node typically generates and disseminates an IGP advertisement that identifies each of the IGP node's neighboring network nodes. In addition, the advertisement also contains one or more “cost” values for each of the neighboring nodes identified in the advertisement. As used herein, a cost value associated with a neighboring node is an arbitrary metric used to determine the relative ease/burden of communicating with that node. The cost values may correspond to various parameters and attributes associated with the neighboring node or with the data link coupled to the node. For example, the cost values may indicate, among other things, a relative preference assigned to the neighboring node, the maximum available bandwidth over a data link coupled to the node, a minimum round-trip time required to communicate with the node, a relative reliability or quality-of-service (QoS) metric associated with the node, etc. In practice, the cost values associated with a link or node are manually assigned, e.g., by a system administrator, and are therefore static in the sense that they do not change values over time.
As noted, IGP advertisements are usually flooded until each IGP node has received an IGP advertisement from each of the other interconnected IGP nodes in the routing area. Furthermore, IGP advertisements are refreshed when a specific timer expires. Then, each of the IGP nodes can construct the same “view” of the network topology by aggregating the received lists of neighboring nodes and cost values. Specifically, each IGP node may input this received routing information to a “shortest path first” (SPF) calculation that determines the lowest-cost network paths that couple the IGP node with each of the other network nodes in the routing area. For example, the Dijkstra algorithm is a conventional technique for performing such a SPF calculation, as described in more detail in Section 12.2.4 of the text book Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
An IGP node may be configured to “protect” network traffic over a given data link or node by providing a repair path (backup path) that circumvents the protected link or node in the event of certain network failures. For instance, in response to identifying that the protected node or data link has become inaccessible or otherwise inoperative, the node immediately upstream to the failed network element (e.g., link or node) may reroute network traffic normally transiting through the failed network element via the repair path. As such, the IGP node does not “drop” received data packets as a result of the network failure. The repair path may be deployed as a fast reroute (FRR) data path, e.g., using Multi-Protocol Label Switching (MPLS) or Internet Protocol (IP) FRR techniques. Examples of MPLS FRR repair paths are described in the IETF Internet Draft draft-ietf-mpls-rsvp-lsp-fastreroute-07.txt, entitled “Fast Reroute Extensions to RSVP-TE for LSP tunnels,” by Pan et al., expiring on February 2005, which is hereby incorporated by reference in its entirety.
The constraint-based SPF (CSPF) algorithm is often used for calculating local repair paths in a routing area. The CSPF algorithm employs conventional SPF calculations subject to a predetermined set of constraints. Broadly stated, the algorithm “prunes” the network topology information input to the SPF calculations so as to remove any links and/or nodes that do not satisfy the set of constraints. First, the algorithm removes the link or node being protected to ensure that the calculated repair path will not include the protected link or node. In the case of a protected data link, any other links that are members of the same shared risk link group (SRLG) as the protected link are also removed from the network topology information input to the CSPF calculations. Next, any data link or network node that fails to satisfy the predetermined set of constraints is excluded from the CSPF calculations. After removing ineligible links and nodes in this manner, the resultant constrained network topology is input to the CSPF calculations. The result of the CSPF calculations is a constrained shortest path that may be used to select a lowest-cost local repair path for the protected node or link.
The predetermined set of constraints used for CSPF calculations are based on statically-configured cost metrics that are typically distributed using IGP protocols. The cost metrics used in the CSPF calculations generally include traditional IGP cost values as well as other statically-configured node and link attributes and parameters, such as link affinities (i.e., administrative attributes assigned to a node or link). For example, the set of constraints may be configured to exclude from the CSPF calculations any nodes and/or data links whose associated cost metrics do not fall within predetermined ranges of cost-metric values. For instance, such a constraint may specify that nodes and data links that support, e.g., a reservable bandwidth below a specified minimum bandwidth should be excluded from the CSPF calculations.
Because CSPF constraints are based on statically-configured cost metrics, the local repair paths derived from the CSPF algorithm may not actually reflect the lowest cost repair paths in the routing area. That is, if the static cost metrics become “out of date” due to changes in the network, then the local repair paths calculated using the CSPF algorithm may not be accurate. There is generally a need to take into account various changes in the network topology when calculating local repair paths to ensure that an IGP node selects the most optimal repair path available for a protected node or link.